package com.hot100.mid;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 组合问题  还是回溯算法
 * @date 2022/8/7 14:21
 */
public class Demo13 {
    //结果集
    List<List<Integer>>  res=new ArrayList<>();
    //每一个满足条件的结果，符合则存到结果集中
    List<Integer>  tempRes=new ArrayList<>();
    //结果总和
    int sum=0;

    public static void main(String[] args) {

    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backTrack(candidates,target,0);
        return res;

    }

    private void backTrack(int[] candidates, int target, int index) {
        if(sum>=target){
            //满足条件的结果存到临时结果集
            if(sum==target){
                res.add(new ArrayList<>(tempRes));
            }
            return;
        }
        for (int i = index; i <candidates.length-1 ; i++) {
            sum+=candidates[index];
            tempRes.add(candidates[index]);
            backTrack(candidates,target,i);
            sum-=candidates[index];
            tempRes.remove(tempRes.size()-1);
        }
    }
}
